package algorithm_demo.demo04.graph;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 图的宽度优先遍历
 * 1. 利用队列实现
 * 2. 从源节点开始依次按照宽度进队列，然后弹出
 * 3. 每弹出一个点，把该节点所有没有进过队列的邻接点放入队列
 * 4. 直到队列为空
 * @author Api
 * @date 2023/2/18 18:29
 */
public class Code01_BFS {

    public static void bfs(Node node){
        if (node == null){
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        //图里面必须有一个set，才能完成遍历，二叉树不用（因为二叉树没有环的问题）
        HashSet<Node> set = new HashSet<>();
        queue.add(node);
        set.add(node);
        while(!queue.isEmpty()){
            Node cur = queue.poll();
            System.out.println(cur.value);
            for(Node next : cur.nexts){
                if (!set.contains(next)){
                    set.add(next);
                    queue.add(next);
                }
            }
        }
    }
}
